package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class MaximumDifferenceBetweenNodeAndAncestor {
	
	//方法一：我自己写的，后序遍历模式
    public int maxAncestorDiff(TreeNode root) {
    	return maxAncestorDiff(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private int maxAncestorDiff(TreeNode node, int max, int min) {
    	max = Math.max(max, node.val);
    	min = Math.min(min, node.val);
    	int maxDiff = max - min;
    		
    	int maxDiffFromLeft = Integer.MIN_VALUE;
    	if(node.left != null) {
    		maxDiffFromLeft = maxAncestorDiff(node.left, max, min);
    	}
    	
    	int maxDiffFromRight = Integer.MIN_VALUE;
    	if(node.right != null) {
    		maxDiffFromRight = maxAncestorDiff(node.right, max, min);
    	}
    	    	
    	return Math.max(Math.max(maxDiffFromLeft, maxDiffFromRight), maxDiff);
    }
    
    //方法二：我自己写的，前序遍历模式
    public int maxAncestorDiff2(TreeNode root) {
    	int[] maxDiff = {Integer.MIN_VALUE};
    	maxAncestorDiff2(root, Integer.MIN_VALUE, Integer.MAX_VALUE, maxDiff);
    	return maxDiff[0];
    }

	private void maxAncestorDiff2(TreeNode node, int max, int min, int[] maxDiff) {
		if(node == null) return;
    	max = Math.max(max, node.val);
    	min = Math.min(min, node.val);
    	maxDiff[0] = Math.max(maxDiff[0], max - min);
		maxAncestorDiff2(node.left, max, min, maxDiff);
		maxAncestorDiff2(node.right, max, min, maxDiff);
	}

	
	//方法三：别人写的，后序遍历模式，更精明简要
    public int maxAncestorDiff3(TreeNode root) {
        return dfs(root, root.val, root.val);
    }

    public int dfs(TreeNode root, int mn, int mx) {
        if (root == null) return mx - mn;
        mx = Math.max(mx, root.val);
        mn = Math.min(mn, root.val);
        return Math.max(dfs(root.left, mn, mx), dfs(root.right, mn, mx));
    }
	
    
}
